/*
? 给定一个m x n 二维字符网格board 和一个字符串单词word 。如果word 存在于网格中，返回 true ；否则，返回 false 。
? 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 */
var exist = function (grid, word) {
    let dfs = (x, y, t) => {
        //? 最后一次还会 +1 因此，条件是大于
        if (t > word.length - 1) {
            return true;
        }
        //? 剪枝条件
        if (
            x < 0 ||
            x >= grid.length ||
            y < 0 ||
            y >= grid[0].length ||
            grid[x][y] != word[t] ||
            grid[x][y] == "#"
        )
            return false;
        let tmp = grid[x][y];
        //? 开始走
        grid[x][y] = "#";
        //? 从四个方向搜索，只要一个方向搜索有结果，那么直接返回 true即可
        let res =
            dfs(x + 1, y, t + 1) || dfs(x, y + 1, t + 1) || dfs(x - 1, y, t + 1) || dfs(x, y - 1, t + 1);
        if (res) return true;
        //? 回溯与递归（重置）
        grid[x][y] = tmp;
        return false;
    };
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == word[0]) {
                let res = dfs(i, j, 0);
                if (res) return true;
            }
        }
    }
    return false;
};
